#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

// 调用基本排序的结果
/*
class Solution {
public:
    int heightChecker(vector<int>& heights) {
      vector<int>temp = heights;
      sort(temp.begin(),temp.end());
      int res = 0;
      for(int i = 0;i < heights.size();++i){
        if(temp[i] != heights[i]){
          ++res;
        }
      }
      return res;
    }
};
*/

// 计数排序版
class Solution {
public:
  int heightChecker(vector<int> &heights) {
    int nums[101] = {0};
    for (auto p = heights.begin(); p != heights.end(); ++p) {
      ++nums[*p];
    }
    int res = 0;
    int pos = -1;
    for (int i = 0; i < 101; ++i) {
      while(nums[i] != 0){
	++pos;
	if(heights[pos] != i){
	  ++res;
	}
	--nums[i];
      }
    }
    return res;
  }
};

int main() {
  Solution s;
  vector<int> a = {1,1,4,2,1,3};
  cout<<s.heightChecker(a)<<endl;
}
